\tracingpages=1
\line{\bf TRIVIA HUNT\hfil CS304, January 1989}
\medskip
\noindent(Teams may have at most four members. For full credit, all answers
should be documented. Answers are due at the beginning of class on Thursday
January~26. Decisions of the judge will be final.)
\bigskip

\newcount\n
\def\\{\medbreak
\advance\n by 1 \item{\bf\number\n.\enspace}}
\def\=#1!{{\unskip\nobreak\hfil\penalty50\hskip2em\hbox{}\nobreak
 \hfil\sl#1\/\parfillskip=0pt\finalhyphendemerits=0\par}}

\\Who were the winners of the first Computer Science Trivia Hunt at
Stanford?\=5 points each!
What did they win?\=10 points!

\\What computer scientist was born on 23 June 1912?\=15 points!
% Alan Turing.

\\In what house did Bill Walsh live when he was a Stanford coach?
Who lives there now?\kern-20pt\=15 points each!
% 903 Cottrell Way, now owned by Prof.~Thomas J. Hughes (chair of Mechanical
% Engineering).

\\What Stanford mathematics professor wrote one of the first papers ever
published about the Tower of Hanoi? What were the dates of his birth
and death? What is his relationship to Professor Floyd of our department?\=15
points each!
% Robert Edgar Allardice was co-author of ``La Tour d'Hano\"\i,'' {\sl
% Proceedings of the Edinburgh Mathematical Society\/ \bf2} (1884), 50--53;
% he was born 2 March 1862, came to Stanford in 1892, became emeritus in 1927,
% and died on 6 May 1928. Floyd lives at 895 Allardice Way.

\\What Stanford computer has its name displayed in stained glass?\=15 points!
% The SUMEX-AIM computer in Stanford Medical School.

\\What are the common names of {\it Formica rufa\/} Linn\ae us?\=10 points each!
% The fallow ant, according to Wheeler, {\sl Ants}, p8, or McCook, {\sl
% The Agriculturnal Ant of Texas}, p152; also called hill ant, wood ant,
% horse ant, and Waldameise (German), according to Donisthorpe, {\sl British
% Ants}, p248.

\\Problem 4 in this year's CS304 is based on an article by Leslie Valiant.
Find all published papers that refer to his article and
give a full citation for every such
paper in the following style: L.~G. Valiant, ``Short monotone formulae for
the majority function,'' {\sl Journal of Algorithms\/ \bf5} (1984), 363--366.%
\=10 points each!
% The following can be found via {\sl Science Citation Index\/}: \
% Joel Friedman, ``Constructing $O(n\log n)$ size monotone formulae for the
% $k$th threshold function of $n$ boolean variables,'' {\sl SIAM Journal on
% Computing\/ \bf15} (1986), 641--654. \
% David S. Johnson, ``The NP-completeness column: An ongoing guide,''
% {\sl Journal of Algorithms\/ \bf7} (1986), 289--305. \
% Ravi B. Boppana, ``Threshold functions and founded depth monotone circuits,''
% {\sl Journal of Computer and System Sciences\/ \bf32} (1986), 222--229. \
% S. A. Lozkin and A. A. Semenov, ``On construction of a complete system
% of compression functions and on complexity of monotone realization of
% threshold boolean functions,'' {\sl Lecture Notes in Computer Science\/
% \bf278} [{\sl Fundamentals of Computatation Theory}, proceedings of FCT87
% in Kazan, USSR] (1987), 297--300.
% And there's another reference in a publication not covered by Science
% Citation Index: Ravi B. Boppana, ``Amplification of probabilistic
% boolean formulas,'' {\sl Proceedings of the 26th Annual Symposium on
% Foundations of Computer Science\/} (1985), 20--29. (This one, unknown
% to Knuth before the Trivia Hunt, is quite relevant to Problem 4.)

\\What identification numbers and dates are stamped on the following
Bench Marks of the U.\thinspace S. Coast and Geodetic Survey on Stanford's
campus? (1)~near a monumental horse; (2)~near a mosaic; (3)~near a potted
umbrella tree; (4)~near the 9th fairway.\=25 points each!
% Bench Marks are shown on the Palo Alto quadrangle of the U.\thinspace S.
% Geological Survey maps in Branner Library. (1)~B151, 1933, at the base of
% the statue of Sherwood, near the Old Red Barn. (2)~R875, 1954, embedded
% in the NE corner of the Stanford Art Museum building. (3)~A151, 1933,
% in concrete steps by the main entrance to the Carnegie Institution of
% Plant Biology. (4)~C151, 1933, on top of a granite rock outcropping
% between the fairway and San Francisquito Creek, not far from the 9th tee
% of Stanford Golf Course.

\\What artist made a painting of Jane Stanford's jewel collection, before
she sold it to help pay faculty salaries? What were the dates of his
birth and death?\=10 points each!
% Astley David Montague Cooper's painting entitled Mrs.~Stanford's Jewel
% Collection hangs in the Stanford Museum, and it says he lived 1856--1924.
% Further research in the Art Library gives more exact dates???

\\What three faculty members of Stanford's Computer Science Department
were born on the same day of the month (but not necessarily in the
same month)?\=30 points!
% John Hennessy, 22 Sep 1952; Yoav Shoham, 22 Jan 1956; Jeffrey Ullman, 22 Nov 1942.

\\What were the date and place of the first battle in the war between Mexico
and the United States?\=10 points each!
% 8 May 1846 at Palo Alto battlefield, Cameron County, Texas.

\\Identify the author and source of the following quotations:\=10 points
for each author!\=15 points for each source!
\vskip1pt
\itemitem{a.}He teaches him to hick and to hack, which they'll do fast
enough of themselves\thinspace\dots---fie upon you.\par
% Shakespeare, Merry Wives of Windsor, Act IV Scene 1 line 68.
\smallskip
\itemitem{b.}As a slow-witted human being I have a very small head and I~had better
learn to live with it and to respect my limitations and give them full credit,
rather than try to ignore them, for the latter vain effort will be punished
by failure.
% Dijkstra, in {\sl Structured Programming}, Academic Press, 1972, page 2.
\smallskip
\itemitem{c.}My thesis is that high-performance systolic arrays can be used
effectively by providing to the user a simple machine abstraction supported
by optimizing compilation techniques. The user sees the systolic array as
an array of sequential processors communicating asynchronously.
% Monica Lam, A Systolic Array Optimizing Compiler (thesis), CMU-CS-87-187, page~2.

\\Obtain xerographic copies of the title pages of the journal articles
in which (1)~Binet published ``Binet's formula'' for Fibonacci numbers;
(2)~Chebyshev published ``Chebyshev's inequality''; (3)~Vandermonde
published ``Vandermonde's convolution''.\=15 points each!
% (1) J. Binet, ``M\'emoire sur l'int\'egration des \'equations lin\'eaires
% aux diff\'e\-ren\-ces finies, d'un ordre quelconque, \`a coefficients
% variables,'' {\sl Comptes Rendus hebdomadaires des s\'eances de l'Acad\'emie des
% Sciences\/} (Paris) {\bf17} (1843), 559--567.
% P.-L. Tch\'ebyshef, ``Des valeurs moyennes,'' {\sl Journal de Math\'matiques
% pures et appliqu\'ees}, series 2, {\bf12} (1867), 177--184; that's a
% translation of the real original, which was in {\sl Matematicheski\u\i\
% Sbornik'\/ \bf2} (1867), 1--9. Stanford's library doesn't own that
% journal, but copies exist at Berkeley, Brown, Columbia, Duke, Illinois,
% Penn, and Yale, as well as the Library of Congress, according to the
% National Union Catalog. With a friend at one of those places it would
% have been possible to fax the page, but nobody did. The article was reprinted
% in Chebyshev's {\sl \OE uvres}, volume~1, 685--694.
% (3)~A. Vandermonde, ``M\'emoire sur des irrationnelles de diff\'erens ordres
% avec une application au cercle,''
% {\sl Histoire de l'Acad\'emie Royale des Sciences\/} (1772), part~1, 71--72;
% {\sl M\'emoires de Math\'ematique et de Physique, Tir\'es des
% Registres de l'Acad\'emie Royale des Sciences\/} (1772), 489--498.

\\What are the next two numbers in the sequence 1, 1, 2, 5, 12, 35, 108, 369, \dots?
Who first computed them? Who first computed the values 108 and 369?\=10 points each!
% Sloane's {\sl Handbook of Integer Sequences\/} identifies this as sequence
% \#561, the number $P_n$ of polyominoes made from $n$~squares (possibly enclosing
% one or more blank squares). Sloane refers to a paper by W.\thinspace F. Lunnon,
% ``Counting polyominoes,'' {\sl Computers in Number Theory\/}
% (Academic Press, 1971), 347--372; Lunnon discusses the history on pages 356--357.
% Chasing down his references, we find that R. Read computed $P_9=1285$ in
% ``??,'' {\sl Canadian Journal of Mathematics\/ \bf14} (1962), 1--20, where
% an incorrect value $P_{10}=4466$ is stated; the correct value $P_{10}=4655$
% must therefore have been computed first by T.\thinspace R. Parkin, L.\thinspace J.
% Lander, and D.\thinspace R. Parkin in unpublished work announced at the
% SIAM fall meeting in 1967 (according to Lunnon). Going back from Read, we find
% an article by Frank Harary, ``Unsolved problems in the enumeration of graphs,''
% {\sl Magyar Tudom\'anyos Akad\'emia, Matematikai Kutat\'o Int\'ezet\'enek,
% K\"ozlem\'enyei\/ \bf5} (1960), 63--95, where he states that Golomb's
% incorrect claim $P_7=109$ was corrected by Stein, Walden, and Williamson,
% who also computed $P_8$. Incidentally, the calculation of $P_n$ seems to
% be fraught with error, since Lunnon claims that Parkin et al.\ had $P_{15}$ wrong.

\\Who coined the term `Artificial Intelligence'? What was research in that field
called previously?\=15 points each!
% John McCarthy chose it late in 1955, and used it in his grant application to
% the Rockefeller Foundation for the 1956 Dartmouth Summer Research Project
% on Artificial Intelligence. Minsky drafted his essay ``Steps toward artificial
% intelligence' after that key conference. Previously the subject had been
% called `automata studies'; see the book {\sl Automata Studies}, edited
% by McCarthy and Shannon, in which W. Ross Ashby writes about `machines with
% ``synthetic'' intellectual powers'. Another term, proposed by Newell and
% Simon, was `complex information processing' (RAND report P-850); see their
% book {\sl Human Problem Solving}, 883--884.

\\Who wrote the report STAN-CS-88-1233? What is that author's favorite color?\=10
points each!
% Ken Ross, our friendly TA, likes ??? best (finger {\tt kar @ polya}).

\\Suppose the words of English were alphabetized from right to left
instead of from left to right, so that all words ending in {\tt a} would
come first, then all words ending in {\tt b}, etc. What would be the
last word in the dictionary? What words would immediately precede and
follow {\tt trivia}? Note: Abbreviations, proper nouns, and hyphenated words
do not count. If your words are not commonly known,
you must state their meaning and give the name of a standard English
dictionary that lists them.\=15 points each!
% According to the `Normal and reversed word list\dots' in the Math/CS library
% (PE1680 N6), which is based on Webster's Second Unabridged and other
% dictionaries, the last word is {\tt bruzz}, a wheelwright's corner chisel.
% That dictionary contains the sequence
% {\tt parathyroprivia}, {\tt trivia}, {\tt Opiconsivia}, {\tt plenalvia},
% {\tt salvia}. The proper name {\tt Opiconsivia} doesn't count; according to
% Webster's Second, {\tt parathyroprivia} is a disease, a deficiency of hormones
% from the parathyroid glands; according to Chambers's Technical Dictionary,
% {\tt plenalvia} is ``impaction of the rumen of cattle''; and {\tt salvia}
% is a genus of herbs that includes sage. Of these words, only {\tt salvia}
% can be found in Webster's Third Unabridged.
\goodbreak
\\Identify the computer language in which each of the following program
fragments is written:\=10 points each!
\vskip-6pt
\def\\#1{\hbox{\it#1\/\kern.05em}} % italic type for identifiers
\def\?{\hfil\break}
\smallskip\itemitem{a.}
\font\sltt=cmsltt10 \font\sytt=cmttsy10 \font\tex=cmtex10 \font\manfnt=manfnt
{\tt +/0=100|{\kern-1pt\sltt V\kern1pt}{\sytt\char2}{\kern-1pt\sltt V\kern1pt}>0}
% APL (from Gilman and Rose, {\sl APL}, exercise 8H).
\smallskip\itemitem{b.}
{\bf procedure} Innerproduct$(a,b)\,$Order:$(k,p)\,$Result:$(y)$; {\bf value} $k$;
{\bf integer} $k,p$; {\bf real} $y,a,b$;\?
{\bf begin real} $s$; $s:=0$; {\bf for} $p:=1$ {\bf step} 1 {\bf until} $k$
{\bf do} $s:=s+a\times b$; $y:=s$ {\bf end} Innerproduct
% Algol 60 (from the original report, {\sl CACM\/ \bf3} (1960), 311).
\smallskip\itemitem{c.}
{\tex\frenchspacing
 stacks\char'30(Array new:3)collect:[:each|OrderedCollection new].\?
(height to: 1 by: -1)do:[:each|(stacks at: 1)addFirst:\?
\null\ \ (Character value:(\$A asciiValue) + each - 1)].}
% Smalltalk (from Kaehler and Patterson, {\sl A Taste of Smalltalk}, p45)
\smallskip\itemitem{d.}
\\{linkage} {\bf class} \\{link};\?
{\bf begin procedure} \\{out};\?
{\bf if} $\\{suc}\mathrel{{=}/{=}}\\{none}$ {\bf then}
{\bf begin} $\\{suc}.\\{pred}\mathrel{{:}-}\\{pred}$;
$\\{pred}.\\{suc}\mathrel{{:}-}\\{suc}$;
$\\{suc}\mathrel{{:}-}\\{pred}\mathrel{{:}-}\\{none}$ {\bf end} \dots {\bf end}
% SIMULA 67 (from Helmut Rolfing, {\sl SIMULA}, p165)
\smallskip\itemitem{e.}
{\tt 10100800\?00E88C03\?00000000\?00000004}
% The ant language of Problem 5.
\smallskip\itemitem{f.}
{\tt IF DAY EXCEEDS 31 THEN SUBTRACT 31 FROM DAY;\?
MOVE "APRIL" TO MONTH; OTHERWISE MOVE "MARCH" TO MONTH.}
% COBOL (from {\sl CACM\/ \bf5} (1962), 210)
\smallskip\itemitem{g.}
{\tex Procedure Mguvar (x,y)\?
\null\ \ \ \ Begin Includes(x,y) ==> Return(False),\?
\null\ \ \ \ \ \ \ \ \ \ Return([x/y])\?
\null\ \ \ \ End}
% Demonstration language in Genesereth and Nilsson, {\sl Logical Foundations
% of Artificial Intelligence}, p68
\smallskip\itemitem{h.}
$\\{top}\,y_2=\\{top}\,y3=.45\,\\{bot}\,y_0$; $z_2=\\{whatever}[z_1,z_{4r}]$;
% {\manfnt METAFONT} (from Knuth's {\manfnt89:;<=>:}\kern1pt{\sl book}, p164)
\smallskip\itemitem{i.}
\par\vskip-\baselineskip\halign{\hskip40pt\tt#\hfill\quad&&\tt#\hfill\quad\cr
R2&&J60\cr &70&J8\cr &40&H0\cr &40&H0\cr &&R2\cr &12&H0\cr &&J65&J68\cr}
% IPL-V (from Sammet, {\sl Programming Languages}, p392)
\smallskip\itemitem{j.}
{\tt\frenchspacing : SQUARE DUP *;\?
: CUBE DUP SQUARE *;\?
: FOURTH DUP CUBE *;}
% FORTH (from Churlian, {\sl Beginning FORTH}, p37); note:
% {\tt\frenchspacing : BETTERFOURTH SQUARE SQUARE;}
\smallskip\itemitem{k.}
{\tt F\"ur j=1(1)n :\?
\tex h\lower2pt\hbox{j-1}+(a\lower2pt\hbox{ij}{\sytt\char2}b\lower2pt\hbox{jk})%
\rlap{==}\kern.25em>\kern.25em h\lower2pt\hbox{j}\?
Ende Index j}
% from Heinz Rutishauser, {\sl Automatische Rechenplantertigung\dots} (1956), p26
\smallskip\itemitem{l.}
{\tt picnic(Day) :- holiday(Day,july\_4), !.\?
picnic(Day) :- weather(Day,fair), weekend(Day).}
% Prolog (from Jean Rogers, {\sl A Prolog Primer}, p118)
\smallskip\itemitem{m.}
\\{Node} = {\bf pointer to} \\{Object};\?
\\{Object} = {\bf record} $\\{key}, x, y$: {\bf integer};
 $\\{left}, \\{right}$: \\{Node} {\bf end};\?
\\{Rectangle} = {\bf pointer to} \\{RectObject};\?
\\{RectObject} = {\bf record}(\\{Object}) $w,h$: {\bf real end};\?
\dots\ {\bf if\/} $p$ {\bf is} \\{Rectangle} {\bf then}
$\\{area}:=p(\\{Rectangle}).w\ast p(\\{Rectangle}).h$; \dots
% Oberon (see N. Wirth, ``From Modulo to Oberon,'' {\sl Software---Practice
% \& Experience\/ \bf18} (1988), 6677)
\smallskip\itemitem{n.}
{\chardef\{=`\{ \chardef\}=`\}
{\tex/increase-x\{xpos radius add /xpos exch def\}def\?
/doCircle\{xpos ypos radius 0 360 circ stroke\}def\?
\{xpos pagewidth le \{doCircle increase-x\}\{exit\}ifelse\}loop}}
% PostScript (from Adobe Systems, {\sl PostScript Language Tutorial
% and Cookbook}, p69--70)
\smallskip\itemitem{o.}
\par\vskip-\baselineskip
\halign{\hskip40pt\hfill$#\null$&#\hfil\cr
\\{testr}[x,p,f,u]\gets&{\bf if\/} $p[x]$ {\bf then} $f[x]$ {\bf else}\cr
&{\bf if\/} $\\{atom}[x]$ {\bf then} $u[\,]$ {\bf else}\cr
&$\\{testr}[\\{cdr}[x],p,f,\lambda{:}\\{testr}[\\{car}[x],p,f,u]]$.\cr}
% McCarthy's publication language for LISP (from Wexelblatt, {\sl History
% of Programming Languages}, p180)

\bye